package gold.enterprise;

public class MicroSoftTwice {

    class TreeNode {
        public int val;
        TreeNode parent;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

//     1
//      \
//      5
//      /\
//     6  7

    /**
     * 思路
     * 如果是叶节点：1.判断是否是左叶节点（cur.parent.left==cur）如果是，则当前节点的parent节点就是后序节点
     * 如果是叶节点：2.判断是否是右叶节点（cur.parent.right==cur）如果是，则为当前节点一直向right溯源第一个为父节点左子树的节点，其根节点即为所求
     * if（cur.parent==cur.parent.parent.left）输出cur.parent.parent
     * <p>
     * 如果不是叶节点：则递归传入其cur.right.left
     *
     * @param cur
     * @return
     */
    public TreeNode findNext(TreeNode cur) {
        if (null == cur) return null;
        if (cur.parent.left == cur) {
            //
        } else if (!(cur.left == null && cur.right == null)) {
            //不是叶节点
            if (null == cur.right) return cur;
            if (null != cur.right.left) return findNext(cur.right.left);
            else return cur.right;
        }

        return null;

    }

    public static void main(String[] args) {
        MicroSoftTwice solution = new MicroSoftTwice();
    }

}
